package com.wlient.basic.designPattern;

import java.util.Arrays;
public class MyArrayList {
    public int[] elem;  //底层数组
    public int useSize; //数组中的有效长度
    public int capacity = 10; //数组长度初始化为10

    public MyArrayList() {  //实现一个构造方法，为数组规定数组长度
        this.useSize = 0;
        this.elem = new int[this.capacity];
    }

    public boolean isEmpty() {
        if (this.useSize == 0) {  //如果数组的有效长度为0，说明数组为空
            return true;
        }
        return false;
    }

    public boolean isFull() {
        if (this.useSize == this.capacity) {
            return true;
        }
        return false;
    }

    //打印顺序表
    public void display() {
        if (isEmpty()) {
            System.out.println("数组为空");
            return;
        }
        for (int i = 0; i < this.useSize; i++) {
            System.out.print(this.elem[i]);
            System.out.print(",");
        }

    }

    //添加数据，pos：位置，value：值
    public void add(int pos, int value) throws Exception{
        //判断pos是否和法
        if (pos < 0 || pos > this.useSize) { //当传来的下标小于0或者大于有效数组长度是，就直接返回，pos不合法
            new Exception("下标不合法");
            return;
        }
        if (isFull()) {
            System.out.println("数组已满，开始扩容");
            this.elem = Arrays.copyOf(this.elem, 2 * this.capacity);
            this.capacity *= 2;
        }

        for (int i = this.useSize; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];
        }
        this.elem[pos] = value;
        this.useSize++;
    }
    public void remove(int pos){
        if (pos < 0 || pos > this.useSize) { //当传来的下标小于0或者大于有效数组长度是，就直接返回，pos不合法
            new Exception("下标不合法");
            return;
        }
        for (int i = pos;i<this.useSize;i++){
            this.elem[i] = this.elem[i+1];
            this.useSize--;
        }
    }

    //判定是否包含某个元素
    public boolean isContains(int value) {
        //先快速排序
        this.elem = quickSort(this.elem, 0, this.useSize - 1);
        //二分查找
        int result = binarySearch(this.elem, value, 0, this.useSize - 1);

        return result == -1 ? false : true;

    }


    //快速排序
    private int[] quickSort(int[] src, int begin, int end) {
        if (begin < end) {
            int key = src[begin];
            int i = begin;
            int j = end;
            while (i < j) {
                while (i < j && src[j] > key) {
                    j--;
                }
                if (i < j) {
                    src[i] = src[j];
                    i++;
                }
                while (i < j && src[i] < key) {
                    i++;
                }
                if (i < j) {
                    src[j] = src[i];
                    j--;
                }
            }
            src[i] = key;
            quickSort(src, begin, i - 1);
            quickSort(src, i + 1, end);
        }
        return src;
    }

    //二分查找
    public int binarySearch(int[] nums, int target, int left, int right) {
        if (left <= right) {
            int mid = left + ((right - left) - 1);
            if (nums[mid] == target) {
                return mid;  //查找成功；
            } else if (nums[mid] > target) {
                return binarySearch(nums, target, left, mid - 1); //新的区间：左半区间；
            } else {
                return binarySearch(nums, target, mid + 1, right); //新的区间: 右半区间；
            }
        }
        return -1;
    }

    public static void main(String[] args) throws Exception {

        MyArrayList myArrayList = new MyArrayList();
        myArrayList.add(0, 22);
        myArrayList.add(1, 45);
        myArrayList.add(2, 48);
        myArrayList.add(3, 5);
        myArrayList.add(4, 65);
        myArrayList.add(5, 25);
        myArrayList.add(6, 15);
        myArrayList.add(7, 5);

        myArrayList.display();
        System.out.println(myArrayList.isContains(15));

        myArrayList.add(9, 5);

        myArrayList.remove(2);

    }
}
